// Package _94__目标和 main
// @Title _94__目标和
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-03-02 19:12
// @Create  2022-03-02 19:12
package main

import (
	"fmt"
)

func findTargetSumWays(nums []int, target int) int {
	var ans int
	var backtrack func(int, int)
	backtrack = func(index, sum int) {
		if index == len(nums) {
			if sum == target {
				ans++
			}
			return
		}
		backtrack(index+1, sum+nums[index])
		backtrack(index+1, sum-nums[index])
	}
	backtrack(0, 0)
	return ans
}

func findTargetSumWaysDP(nums []int, target int) int {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	diff := sum - target
	if diff < 0 || diff%2 == 1 {
		return 0
	}
	n, neg := len(nums), diff/2
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, neg+1)
	}
	dp[0][0] = 1
	for i, num := range nums {
		for j := 0; j <= neg; j++ {
			dp[i+1][j] = dp[i][j]
			if j >= num {
				dp[i+1][j] += dp[i][j-num]
			}
		}
	}
	return dp[n][neg]
}

func main() {
	fmt.Println(findTargetSumWays([]int{1, 1, 1}, 2))
}
